In a multi-tenant datacenter environment, typically an edge appliance, such as an edge router, is deployed per tenant to handle all the “North-South” (in and out of the tenant network) traffic. Note that a tenant is any application that needs its own secure and exclusive virtual computing environment. The edge appliance also serves as the main Policy Enforcement Point (PEP) for the tenant network. Traditional PEP services typically provided by this edge appliance include firewall and network address translation (NAT). Due to the sheer amount of traffic processing coupled with the policy enforcement responsibility, this edge appliance often becomes a bottleneck for the network and hampers scalability. Moreover, by the time egress traffic from the tenant side reaches the edge, it may have traversed multiple intermediate routers and service nodes in the datacenter, both virtual and physical, which may have altered the traffic parameters, such as source/destination address or port. As a result, implementing multiple PEP points and distributing the edge policy to these multiple PEP points can be an issue.